package com.xyhuo.leetcode.january;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU缓存
 * https://leetcode.cn/problems/lru-cache/
 *
 * @time 2024/1/19
 */
public class LRUCache {

//    public static void main(String[] args) {
//        LRUCache cache = new LRUCache(2);
//        cache.put(2, 1);
//        cache.put(1, 1);
//        cache.put(2, 3);
//        cache.put(4, 1);
//        cache.get(1);
//        cache.get(2);
//    }

    class DoubleLinkedListItem {
        public int index;
        public int val;
        public DoubleLinkedListItem pre;
        public DoubleLinkedListItem next;

        DoubleLinkedListItem(int index, int val) {
            this.index = index;
            this.val = val;
        }
    }

    private DoubleLinkedListItem head;
    private DoubleLinkedListItem tail;

    private int capacity;

    private Map<Integer, DoubleLinkedListItem> map = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new DoubleLinkedListItem(-1, 0);
        tail = new DoubleLinkedListItem(-1, 0);
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        DoubleLinkedListItem item = removeItem(key);
        addTail(item);
        return map.get(key).val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            DoubleLinkedListItem item = map.get(key);
            item.val = value;
            removeItem(key);
            addTail(item);
        } else {
            DoubleLinkedListItem newItem = new DoubleLinkedListItem(key, value);
            if (map.size() == capacity) {
                int removeKey = head.next.index;
                removeItem(removeKey);
                map.remove(removeKey);
            }
            addTail(newItem);
            map.put(key, newItem);
        }
    }

    private DoubleLinkedListItem removeItem(int key) {
        DoubleLinkedListItem item = map.get(key);
        DoubleLinkedListItem pre = item.pre;
        DoubleLinkedListItem next = item.next;
        pre.next = next;
        next.pre = pre;
        return item;
    }

    private void addTail(DoubleLinkedListItem newItem) {
        tail.pre.next = newItem;
        newItem.pre = tail.pre;
        newItem.next = tail;
        tail.pre = newItem;
    }
}
